package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/11/29.<br><br>
 *
 * 中等：二叉树展开为链表
 */
public class Topic114 {

    public static void main(String[] args) {
        Topic114 instance = new Topic114();
        TreeNode root;

        root = Util.createTree(Arrays.asList(1, 2, 5, 3, 4, null, 6));
        instance.flatten(root);
        Util.preTravelTree(root);
    }

    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.left != null) {
                TreeNode left = cur.left;
                TreeNode right = left;
                while (right.right != null) {
                    right = right.right;
                }

                right.right = cur.right;
                cur.right = left;
                cur.left = null;
            }
            else {
                cur = cur.right;
            }
        }
    }

    public void flatten2(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        helper(root, list);

        for(int i = 1; i < list.size(); i++) {
            list.get(i - 1).right = list.get(i);
            list.get(i - 1).left = null;
        }
    }

    private void helper(TreeNode root, List<TreeNode> list) {
        if(root == null) {
            return ;
        }

        list.add(root);
        helper(root.left, list);
        helper(root.right, list);
    }
}
